#include <stdio.h>
#include <malloc.h>


//二叉搜索树 BST
//1.定义一个数据结构
typedef int ElementType;
typedef struct node *BST;
struct node{
    //1.数据项
    ElementType  data;
    //2.地址项
    struct node *left;
    struct node *right;
};

//2.操作

//2.1 creatBST：从空树开始创建一个树
//插入分为两部分：（1）查找到合适的位置（通过“遍历”） （2）执行插入
/*
 * 函数名：creatBST()
 * 输入：数值,根结点
  * 输出：返回创建好的树的根结点
 * */
BST creatBST(BST root,ElementType value){
    //1.假设找到合适的位置，现在执行插入
    //空树
    if(root ==NULL){
        //插入
        //插入的步骤：（1）创建结点，存放数值 （2）链接结点（放置到合适的位置）
        root = malloc(sizeof(struct node));
        root->data=value;
        root->left=NULL;
        root->right=NULL;
        return root;
    }
    //2.value>root.data value 插入到右子树
    if(value>root->data){
       root->right= creatBST(root->right,value);
    }
    //3. value<root.data value插入到左子树
    if(value<root->data)
      root->left =  creatBST(root->left,value);
    return root;

}

//2.2查找
//2.2.1 查找特定值
/*
 *  (1) value>currentRoot.data 往右
 *  （2）value< currentRoot.data  往左
 *  （3）value= currentRoot.data 找到结点 返回该结点
 *
 *
 *
 * */

BST findValue(BST root,ElementType value){
    if(root==NULL)
        return NULL;
    if(value==root->data)
        return root;
    if(value>root->data)
       return findValue(root->right,value);
    if(value<root->data)
       return findValue(root->left,value);
}
//2.2.2 查找最大值
/*
 * 对于二叉搜索树而言，最大的数值存储在树的最右端的结点上
 * 函数名：findMax()
 * 输入：待搜索的树（其实传递的是根结点）
 * 输出：返回包含最大值的结点
 * */
BST findMax(BST root){
    //（1）寻找最大值的前提是树不为空,如果树为空，单独处理
    if(root==NULL){
        return NULL;
    }
    //（2）如果树不为空，一直往右，找到最右端的结点
    //1.定义一个指针，指向根结点
    BST current =root;
    //2.如果当前的指针所指向的结点有右子结点，则指针指向右子结点，直到右子结点为空
    while(current->right!=NULL){
        current =current->right;
    }
    return current;
}
//2.2.3 查找最小值
//一直往左找
BST findMin(BST root){
    if(root==NULL)
        return NULL;
    BST current=root;
    while(current->left!=NULL)
        current=current->left;
    return current;
}


//2.5 删除
/*、
 *
 * 删除算法：给定一个值value，然后在树里面删除包含该值的结点
 * 删除的前提：树不为空
 * 删除过程：
 * （1）根据给定值找到该结点（找到结点才能删除）
 *      找结点的方法：通过比较value与当前的结点进行比较
 *      1.1 如果value>node.data  在该结点的右子树里 进行删除
 *      1.2 if(value<node.data) 在该结点左子树里进行删除
 *      1.3 if（value == node.data）找到该结点node，对该结点node执行删除，即步骤（2）
 * （2）找到结点node进行删除
 *     2.1 node.left&&node.right 都存在，我们将将其转换为第（2.2）种情况
 *          转化方式：1. 在左子树node.left找最大值的结点
 *                  2. 在右子树node.right找最小值的结点
 *                  （任选其一）
 *          将该结点的值重新赋值成其左子树的最大值或右子树的最小值   node.data =Max(node.left)||node.data =Min(node.right)
 *    2.2 node.left || node.right 至少有一个不存在
 *        此时，我们将该结点赋值成存在的子结点 node =node.left 谁存在链接谁
 * */
/*
 * 函数名：deleteNode()
 * 输入：树（树的根），删除的值
 * 输出：删除后树的根
 * */
BST deleteNode(BST bst,ElementType value){
    //1.树为空/结点为空
    if(bst ==NULL){
        printf("树为空，无法删除\n");
        return NULL;
    }
    //2.找结点
    if(value>bst->data)
        bst->right = deleteNode(bst->right,value);
    else if(value <bst->data)
        bst->left = deleteNode(bst->left,value);
    else{//3.找到结点，删结点
        BST tmp=NULL;
        //3.1 左右子结点都存在，则转换为3.2的清空
        if(bst->left&&bst->right){
            //找右子树的最小值
             tmp = findMin(bst->right);
            //将待删除位置结点的值赋值成找到的最小值
            bst->data=tmp->data;
           bst->right = deleteNode(bst->right,bst->data);
        } else{//至少一个子结点为空，这种情况下真正执行删除
            tmp =bst;//tmp是待会儿要删除的结点，保存好该结点，用于释放该结点的空间
            //从逻辑上在树的结构里删除该结点
            if(bst->left==NULL){
                bst=bst->right;
            } else{
                bst =bst->left;
            }
            //释放空间 ，在内存上释放掉不需要的这个结点空间
            free(tmp);
        }

    }
    return bst;
}

int main() {

    //1.创建一个二叉树
   BST bst =NULL;
   bst = creatBST(bst,4);
   bst = creatBST(bst,5);
   bst = creatBST(bst,1);
   bst = creatBST(bst,3);
   bst = creatBST(bst,7);
   bst = creatBST(bst,9);
    //2.测试方法
    BST minNode = findMin(bst);
    printf("最小值是%d\n",minNode->data);

    BST maxNode = findMax(bst);
    printf("最大值是%d\n",maxNode->data);

    BST node = findValue(bst,23);
    if(node){
        printf("结点找到\n");
    } else
        printf("结点未找到\n");
  //  printf("最小值是%d\n",minNode->data);
    //printf("Hello, World!\n");
    deleteNode(bst,3);
    printf("删除值为3的结点\n");

    return 0;
}
